package q115_numDistinct;

public class Solution {
    public int numDistinct(String s, String t) {
        int[][] dp = new int[s.length() + 1][t.length() + 1];
        // 注意初始化时 dp[i][0] = 1;
        for (int i = 0; i < s.length() + 1; i++) {
            dp[i][0] = 1;
        }

        for (int i = 1; i < s.length() + 1; i++) {
            for (int j = 1; j < t.length() + 1; j++) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    // dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                    // 代表最后一个字符匹配上了 但为什么是dp[i - 1][j - 1] + dp[i - 1][j];
                    // 因为考虑到t的最后字符j - 1位置 匹配过程中
                    // 最后一个字符可以不用s的最后一个字符i - 1匹配 之前的字符里面如果有匹配也可以算匹配成功
                    // 所以匹配成功时 dp代表匹配的个数 也就是当前匹配上了的和之前匹配的个数之和
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                }else{
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        return dp[s.length()][t.length()];
    }

}
